﻿// 哈夫曼树与文件压缩.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
typedef enum { LEFT, RIGHT }Ad;//一个节点是他双亲的左孩子还是右孩子
typedef struct Bitree {
	char letter;
	Bitree* left, * right, * parent;
	int weight;//此程序中字符的权值通过某个字符在文本中出现的次数来表示
	Ad ad;
}Bitree;
typedef struct Help_HFM {//记录了一个二叉树节点对应的指针和其权值的链表
	int weight;
	Bitree* Bt;
	Help_HFM* next;
}Help_HFM;
typedef bool Bite;//用bool型变量来表示哈夫曼编码中的一个位
typedef struct Sqstack {//存储二叉树指针的栈的栈顶栈底和栈的最大元素个数
	Bitree** front, ** rear;
	int maxisize;
} Sqstack;
Sqstack* createSq(int maxisize = 100) {//创造一个存储二叉树节点指针栈
	Sqstack* Sq;
	if (!(Sq = (Sqstack*)malloc(sizeof(Sqstack)))) exit(1);//是否成功分配内存
	Sq->maxisize = maxisize;
	if (!(Sq->front = (Bitree**)malloc(sizeof(Bitree*) * Sq->maxisize))) exit(1);//是否成功分配内存
	Sq->rear = Sq->front;
	return Sq;
}
int push(Sqstack* Sq, Bitree* list) {//将一个二叉树指针入栈
	if (Sq->rear - Sq->front > Sq->maxisize) exit(1);//判栈满
	*(Sq->rear) = list;
	Sq->rear = Sq->rear + 1;
	return 0;
}
Bitree* pop(Sqstack* Sq) {//将一个二叉树指针出栈
	if (Sq->front != Sq->rear) exit(1);//判栈空
	Bitree* list = *((Sq->rear)--);
	return list;
}
Help_HFM* createHH(int weight = 0, Bitree* Bt = NULL, Help_HFM* next = NULL) {//创造一个链表节点
	Help_HFM* HH;
	if (!(HH = (Help_HFM*)malloc(sizeof(Help_HFM)))) exit(1);//是否成功分配内存
	HH->weight = weight;
	HH->Bt = Bt;
	HH->next = next;
	return HH;
}
int insertHH(Help_HFM* head, Help_HFM* HH) {//将某个节点插入链表，链表元素按weight从小到大排列
	while (head->next != NULL) {
		if (head->next->weight >= HH->weight) {
			Help_HFM* a = head->next;
			head->next = HH;
			HH->next = a;
			return 0;
		}
		head = head->next;
	}
	head->next = HH;
	return 0;
}
Bitree* createBt(char letter = '\0', int weight = 1, Bitree* left = NULL, Bitree* right = NULL, Ad ad = LEFT, Bitree* parent = NULL) {//创造一个二叉树节点
	Bitree* Bt;
	if (!(Bt = (Bitree*)malloc(sizeof(Bitree)))) exit(1);//是否成功分配内存
	Bt->letter = letter;
	Bt->weight = weight;
	Bt->left = left;
	Bt->right = right;
	Bt->parent = parent;
	Bt->ad = ad;
	return Bt;
}
Help_HFM* getweight(char* infilename, Bitree* all_letter[128]) {//读取文件中的各个字符出现次数并以文件(weight.txt)形式输出，创造一个辅助构建哈夫曼树的链表，返回值为其头指针
	Help_HFM* head = createHH();
	char letter;
	FILE* w_fp = fopen("weight.txt", "w + "), * in;
	if (!(in = fopen(infilename, "r"))) exit(1);//若没找到要压缩的文件，退出
	while (!feof(in)) {//为文件中出现过的字符创建一个叶子节点，并统计其出现次数存入weight中 
		fscanf(in, "%c", &letter);
		if (all_letter[letter] == NULL) {
			Bitree* Bt = createBt(letter);
			all_letter[letter] = Bt;
		}
		else all_letter[letter]->weight = all_letter[letter]->weight + 1;
	}
	for (char i = 32; i <= 126; i++) {//完成统计，根据每个字符出现次数，创造一个辅助构建哈夫曼树的链表
		if (all_letter[i] != NULL) {
			Help_HFM* HH = createHH(all_letter[i]->weight, all_letter[i]);
			insertHH(head, HH);
			fprintf(w_fp, "%c %d ", i, all_letter[i]->weight);
		}
	}
	fclose(w_fp);
	return head;
}
Help_HFM* readweight(FILE* w_fp, Bitree* all_letter[128]) {//读取weight.txt文件，创造一个辅助构建哈夫曼树的链表，返回值为其头指针
	Help_HFM* head = createHH();
	int weight;
	char letter;
	while (!feof(w_fp)) {//根据每个字符的出现次数不同，产生叶子节点；并将其写入链表
		fscanf(w_fp, "%c %d ", &letter, &weight);
		Bitree* Bt = createBt(letter, weight);
		Help_HFM* HH = createHH(weight, Bt);
		insertHH(head, HH);
		all_letter[letter] = Bt;
	}
	return head;
}
Bitree* createHFM(Help_HFM* head) {//通过HH构建哈夫曼树，并销毁HH，返回值为哈夫曼树根节点
	Bitree* left, * right, * parent;
	Help_HFM* H1, * H2, * NH;
	while (head->next->next != NULL) {//若链表中有两个以上元素,创造新节点作为头两个节点(权值最小的两个节点)的双亲节点,将两个节点删除并将新节点有序插入链表；
		H1 = head->next;
		H2 = H1->next;
		left = H1->Bt;
		right = H2->Bt;
		right->ad = RIGHT;
		parent = createBt('\0', 0, left, right);
		left->parent = parent;
		right->parent = parent;
		NH = createHH(H1->weight + H2->weight, parent);
		head->next = H2->next;
		free(H1); free(H2);
		insertHH(head, NH);
	}
	free(head->next); free(head);//若链表中只有一个节点，其为哈夫曼树的根节点，代表哈夫曼树创建完成，销毁链表
	return parent;
}
int getHFMcode(Bitree* HFM, Bite* HFMcode[128], Bitree* all_letter[128], int codelong[128]) {//从叶子节点通过parent指针遍历哈夫曼树取得所有字符的哈夫曼编码
	int length = 0;//length为一个字符编码的长度
	Bite current[128];//current为临时存储字符编码的逆的数组，可以知道，一个字符编码不可能超过128个bite(总字符数)
	for (int i = 32; i <= 126; i++) {//从32到126为可视的字符，将它们的哈夫曼编码取出
		length = 0;
		if (all_letter[i] != NULL) {
			Bitree* k = all_letter[i];
			while (k->parent != NULL) {
				length++;
				if (k->ad == LEFT) current[length - 1] = 0;
				else current[length - 1] = 1;
				k = k->parent;
			}
			if (!(HFMcode[i] = (Bite*)malloc(sizeof(Bite) * length))) exit(1);//是否成功分配内存
			for (int y = 0; y <= length - 1; y++)
				HFMcode[i][y] = current[length - 1 - y];
			codelong[i] = length;
		}
	}
	return 0;
}
int getorder(char* order, char* object, char* output, char* str) {//读取用户输入的指令
Loop1://输入指令的位置
	printf("请输入指令:(20个字符内)\n");
	scanf("%s", order);
	if (strlen(order) >= 20) goto Loop1;//输入字符串过长，重新输入
	if (strcmp(order, "compress") == 0 || strcmp(order, "decompress") == 0) {
	Loop2://输入操作文件名的位置
		printf("请输入操作文件名:（20个字符内）\n");
		scanf("%s", object);
		if (strlen(object) >= 20) goto Loop2;//输入字符串过长，重新输入
	Loop3://输入结果文件名的位置
		printf("请输入结果文件名:（20个字符内）\n");
		scanf("%s", output);
		if (strlen(output) >= 20) goto Loop3;//输入字符串过长，重新输入
		return 0;
	}
	if (strcmp(order, "find") == 0) {
	Loop4://输入操作文件名的位置
		printf("请输入操作文件名:（20个字符内）\n");
		scanf("%s", object);
		if (strlen(object) >= 20) goto Loop4;//输入字符串过长，重新输入
	Loop5://输入待查找字符串的位置
		printf("请输入查找的字符:（20个字符内）\n");
		scanf("%s", str);
		if (strlen(str) >= 20) goto Loop5;//输入字符串过长，重新输入
		return 0;
	}
	goto Loop1;//没有这条指令，重新输入
	return 0;
}
FILE* compress(char* infilename, char* outfilename, Bite* HFMcode[128], int codelong[128]) {//压缩文件，返回值为指向结果的指针
	FILE* in, * out;//in为需要压缩的文件，out为压缩后的文件
	if (!(in = fopen(infilename, "r"))) exit(1);//若没找到要压缩的文件，退出
	if (!(out = fopen(outfilename, "wb+"))) exit(1);//若未成功创建文件，退出
	unsigned char current, ch = 0, last_ch = 0, unByte_number = 0;
	int last_Bite = 0, Byte = 0, next_Bite = 0;
	//last_Bite与last_ch分别存储之前多余Bite(未达到8位，即一个字节)的数目和编码
	//Bite为本次操作能组成的字节数，next_Bite为本次操作后多余的Bite数目
	fread(&current, sizeof(char), 1, in);
	while (!feof(in)) {//读入字符，找到其哈夫曼编码，每凑够8个Bite通过位运算编写成一个char型变量写入数组
		if (current >= 32 && current <= 126) {
			if (codelong[current] == 0) exit(1);//没有这个字符的编码，退出
			ch = last_ch;
			Byte = (last_Bite + codelong[current]) / 8;
			next_Bite = (last_Bite + codelong[current]) % 8;
			if (Byte == 0) {
				for (int i = 0; i <= codelong[current] - 1; i++)
					last_ch = last_ch | (HFMcode[current][i] << (7 - last_Bite - i));
			}
			else {
				for (int i = 0; i <= 8 - last_Bite - 1; i++)
					ch = ch | (HFMcode[current][i] << (7 - last_Bite - i));
				fwrite(&ch, sizeof(char), 1, out);
				ch = 0;
				for (int i1 = 1; i1 <= Byte - 1; i1++) {
					for (int i2 = 0; i2 <= 7; i2++)
						ch = ch | (HFMcode[current][i1 * 8 + i2 - last_Bite] << (7 - i2));
					fwrite(&ch, sizeof(char), 1, out);
					ch = 0;
				}
				last_ch = 0;
				for (int i = 0; i <= next_Bite - 1; i++)
					last_ch = last_ch | (HFMcode[current][Byte * 8 - last_Bite + i] << (7 - i));
			}
			last_Bite = next_Bite;
		}
		fread(&current, sizeof(char), 1, in);
	}
	fwrite(&last_ch, sizeof(char), 1, out);//最后未凑够一个字节的补零后写入
	last_ch = last_Bite + 30;
	fwrite(&last_ch, sizeof(char), 1, out);//结尾写入一个字节来记录补零了多少位
	fclose(in);
	return out;
}
FILE* decompress(char* infilename, char* outfilename, Bitree* HFM) {//解压文件，返回值为指向结果的指针
	FILE* in, * out;//in为需要解压的文件，out为解压后的文件
	if (!(in = fopen(infilename, "rb"))) exit(1);//若没找到要解压的文件，退出
	if (!(out = fopen(outfilename, "w+"))) exit(1);//若未成功创建文件，退出
	Bite current;
	unsigned char ch, key;
	Bitree* Bt;
	int i = 0, end = 8;
	while (!feof(in)) {//逐位读入编码并通过哈夫曼树(0则指针指向左孩子，1则右孩子)找到对应的字符写入解压文件
		Bt = HFM;
		while (Bt->left != NULL || Bt->right != NULL) {
			fread(&ch, sizeof(char), 1, in);
			current = ch & (1 << (7 - i));
			i = (i + 1) % 8;
			if (i != 0) fseek(in, -sizeof(char), SEEK_CUR);
			if (current == 0) Bt = Bt->left;
			else Bt = Bt->right;
		}
		fseek(in, sizeof(char), SEEK_CUR);//判断文件是否读入结束
		fread(&key, sizeof(char), 1, in);
		if (feof(in)) end = key - 30;
		fseek(in, -sizeof(char) * 2, SEEK_CUR);
		if (i == end) return 0;
		fprintf(out, "%c", Bt->letter);
	}
	fclose(in);
	return out;
}
int findmove(Bite* code, int* move, int length2) {//求出BM未匹配时需要跳转的位数
	int* bad, * good, * last_next, j = 0;
	if (!(bad = (int*)malloc(sizeof(int) * length2))) exit(1);
	if (!(good = (int*)malloc(sizeof(int) * length2))) exit(1);
	if (!(last_next = (int*)malloc(sizeof(int) * length2))) exit(1);
	for (int i1 = length2 - 1; i1 >= 0; i1--) {//求出坏字符规则转跳的位置
		bad[i1] = -1;
		for (int i2 = i1 - 1; i2 >= 0; i2--) {
			if (code[i1] == code[i2]) {
				bad[i1] = i2;
				break;
			}
		}
	}
	for (int i = length2 - 2; i >= 0; i--) {//从267行到290行为求出好后缀规则转跳的位置
		if (code[i] == code[length2 - 1]) {
			last_next[j] = i;
			j++;
		}
	}
	good[length2 - 1] = last_next[0];
	for (int i1 = length2 - 2; i1 >= 0; i1--) {
		int i2 = 0;
		while (i2 <= j - 1) {
			int l = last_next[i2] - 1;
			if (l >= 0 && code[i1] != code[l]) {
				for (int i3 = i2; i3 <= j - 2; i3++)
					last_next[i3] = last_next[i3 + 1];
				j--;
			}
			else {
				last_next[i2] = l;
				i2++;
			}
		}
		good[i1] = last_next[0];
		if (j == 0) good[i1] = i1 - length2;
	}
	for (int i = 0; i <= length2 - 1; i++) {//取坏字符和好后缀转跳位数最大的作为转跳值
		int a = i - good[i], b = i - bad[i];
		if (a >= b) move[i] = a;
		else move[i] = b;
	}
	move[length2] = 1;
	return 0;
}
int BM(char* object, int* move, int length2, Bite* code) {//通过BM算法转跳
	FILE* fp;
	if (!(fp = fopen(object, "rb"))) exit(1);
	int  j = 0, k = length2, last_Bite = 0, next_Bite = 0, Byte = 0, head = 0, tail = length2 - 1;
	char ch, is_countinue;
	Bite* current = (Bite*)malloc(sizeof(Bite) * (length2 + 1)), Bi;
	//通过一个大小为length2+1环状的数组存储，head和tail为其头尾位置
	//last_Bite为之前操作多读取(未凑够一个字节)的Bite个数，next_Bite为本次操作多读取的
    //k为每次子串的位移位数
Loop1:
	fseek(fp, sizeof(char) * 1, SEEK_CUR);
	fread(&ch, sizeof(char), 1, fp);
	if (!feof(fp)) {//文件未结束寻找对应编码
		fseek(fp, -sizeof(char) * 2, SEEK_CUR);
		tail = (head + length2 - 1) % (length2 + 1);//从313行到336行根据k值刷新环状数组
		head = (head + k) % (length2 + 1);
		next_Bite = (last_Bite + k) % 8;
		Byte = (last_Bite + k) / 8;
		if (Byte == 0) {
			fread(&ch, sizeof(char), 1, fp);
			for (int i = 0; i <= k - 1; i++)
				current[(tail + i + 1) % (length2 + 1)] = ch & (1 << (7 - i - last_Bite));
			fseek(fp, -sizeof(char), SEEK_CUR);
		}
		else {
			fread(&ch, sizeof(char), 1, fp);
			for (int i = 0; i <= 8 - last_Bite - 1; i++)
				current[(tail + 1 + i) % (length2 + 1)] = ch & (1 << (7 - last_Bite - i));
			for (int i1 = 1; i1 <= Byte - 1; i1++) {
				fread(&ch, sizeof(char), 1, fp);
				for (int i2 = 0; i2 <= 7; i2++)
					current[(tail + 1 + i1 * 8 + i2 - last_Bite) % (length2 + 1)] = ch & (1 << (7 - i2));
			}
			fread(&ch, sizeof(char), 1, fp);
			for (int i = 0; i <= next_Bite - 1; i++)
				current[(tail + i + 1 + Byte * 8 - last_Bite) % (length2 + 1)] = ch & (1 << (7 - i));
			fseek(fp, -sizeof(char), SEEK_CUR);
		}
		last_Bite = next_Bite;
		for (int i1 = length2 - 1, i0 = length2 - 1; i0 >= 0 - 1, i1 >= 0; i1--, i0--) {//比较刷新后的环形数组是否与子串一致
			if (current[(head + i0) % (length2 + 1)] != code[i1]) {//不一致求出k值并重复操作
				k = move[i1 + 1];
				goto Loop1;
			}
		}
	}
	else {//文件结束，结束所有操作
		printf("\n没有找到");
		free(current);
		return 0;
	}
	fseek(fp, -sizeof(char) * length2 / 8, SEEK_CUR);
	for (int i = 1; i <= length2 / 8 + 1; i++) {
		fread(&ch, sizeof(char), 1, fp);
		for (int i2 = 0; i2 <= 7; i2++) {
			Bi = ch & (1 << (7 - i2));
			printf("%d", Bi);
		}
	}
	printf("\n");
Loop2:
	fseek(fp, -sizeof(char), SEEK_CUR);
	printf("是否继续？(y or n)");
	scanf(" %c", &is_countinue);
	if (is_countinue == 'y') goto Loop1;
	if (is_countinue != 'y' && is_countinue != 'n') goto Loop2;//不能辨识的指令要求重新输入
	free(current);
	return 0;
}
int destoryHFM(Bitree* T) {//后序遍历删除哈夫曼树
	Sqstack* Sq = createSq();
	Bitree* current = T;
Loop://遍历到非叶子节点则入栈，遍历到叶子节点删除后出栈
	while (current->left != NULL) {
		push(Sq, current);
		current = current->left;
	}
	if (current->right != NULL) {
		push(Sq, current);
		current = current->right;
	}
	else {
		free(current);
		current = pop(Sq);
	}
	if (Sq->front < Sq->rear) goto Loop;//栈空为结束条件
	return 0;
}
int main() {
	char order[20], object[20], output[20], str[20];
	//order为指令，有：compress为压缩指令，decompress为解压指令，find为查找指令
	//object为要进行操作的文件；若有查找操作，str为要查找的字符串
	FILE* outcome;
	Bitree* HFM, * all_letter[128] = { NULL };//HFM为哈夫曼树的根节点，all_letter为每个字符叶子节点的指针
	Bite* HFMcode[128], * code;//HFMcode记录每个字符的哈夫曼编码,code为待查找字符串哈夫曼编码
	int codelong[128] = { 0 }, * move;//codelong记录每个字符哈夫曼编码长度，move[i]为BM算法中字串某处匹配失败转跳的地址
	getorder(order, object, output, str);
	if (strcmp(order, "compress") == 0) {
		Help_HFM* HH = getweight(object, all_letter);
		HFM = createHFM(HH);
		getHFMcode(HFM, HFMcode, all_letter, codelong);
		outcome = compress(object, output, HFMcode, codelong);
	}
	if (strcmp(order, "decompress") == 0) {
		FILE* w_fp;//w_fp是记录字符权值的文件
		if (!(w_fp = fopen("weight.txt", "r"))) exit(1);//若未找到记录权值的文件，退出
		Help_HFM* HH = readweight(w_fp, all_letter);
		HFM = createHFM(HH);
		outcome = decompress(object, output, HFM);
		fclose(w_fp);
	}
	if (strcmp(order, "find") == 0) {
		FILE* w_fp;//w_fp是记录字符权值的文件
		if (!(w_fp = fopen("weight.txt", "r"))) exit(1);//若未找到记录权值的文件，退出
		Help_HFM* HH = readweight(w_fp, all_letter);
		HFM = createHFM(HH);
		getHFMcode(HFM, HFMcode, all_letter, codelong);
		int  j = 0, length1 = strlen(str), length2 = 0;//length1为字符串长度，length2为其编码长度
		for (int i = 0; i <= length1 - 1; i++)//从417行到422行，求得待查找字符串的哈夫曼编码
			length2 = length2 + codelong[str[i]];
		if (!(code = (Bite*)malloc(sizeof(Bite) * length2))) exit(1);
		for (int i0 = 0; i0 <= length1 - 1; i0++)
			for (int i1 = 0; i1 <= codelong[str[i0]] - 1; i1++, j++)
				code[j] = HFMcode[str[i0]][i1];
		move = (int*)malloc(sizeof(int) * length2);
		findmove(code, move, length2);
		BM(object, move, length2, code);
		fclose(w_fp);
	}
	destoryHFM(HFM);
	free(move); free(code);
	fclose(outcome);
	return 0;
}